public class 盈利计划 {

    public static int mod = 1000000007;

    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
        for (int i = 0; i <= group.length; i++) {
            for (int j = 0; j <= n; j++) {
                for (int k = 0; k <= minProfit; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }
        return dfs1(n,minProfit,group,profit,0,dp);
    }

    private int dfs1(int n, int minProfit, int[] group, int[] profit, int pos,int[][][] dp ) {
        // 没人了
        if (n == 0) {
            return minProfit <= 0 ? 1 : 0;
        }
        // 没有工作了
        if (pos == group.length) {
            return minProfit <= 0 ? 1 : 0;
        }

        if (dp[pos][n][minProfit] != 0) {
            return dp[pos][n][minProfit];
        }
        // 不干这个工作
        int ans = 0;
        ans = dfs1(n,minProfit,group,profit,pos + 1,dp ) % mod;

        // 干这个工作
        if (n >= group[pos]) {
            ans = (ans +  dfs1(n - group[pos],Math.max(minProfit - profit[pos],0),group,profit,pos + 1,dp) % mod) % mod;
        }
        dp[pos][n][minProfit] = ans;
        return ans;
    }

    public int profitableSchemes1(int n, int minProfit, int[] group, int[] profit) {
        int[][][] dp = new int[group.length + 1][n + 1][minProfit + 1];
        for (int j = 0; j <= n; j++) {
            for (int k = 0; k <= minProfit; k++) {
                dp[group.length][j][0] = 1;
            }
        }
        for (int i = group.length - 1; i >= 0; i--) {
            for (int j = n; j >= 0; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[i][j][k] = dp[i + 1][j][k] % mod;
                    if (j >= group[i]) {
                        dp[i][j][k] = (dp[i][j][k] + dp[i + 1][j - group[i]][Math.max(k - profit[i],0)] % mod) % mod;
                    }
                }
            }
        }
        return dp[0][n][minProfit];
    }

    public int profitableSchemes2(int n, int minProfit, int[] group, int[] profit) {
        int[][] dp = new int[n + 1][minProfit + 1];
        for (int j = 0; j <= n; j++) {
                dp[j][0] = 1;
        }
        for (int i = group.length - 1; i >= 0; i--) {
            for (int j = n; j >= group[i]; j--) {
                for (int k = minProfit; k >= 0; k--) {
                    dp[j][k] = (dp[j][k] + dp[j - group[i]][Math.max(k - profit[i],0)] % mod) % mod;
                }
            }
        }
        return dp[n][minProfit];
    }
}
